Форда — Фалкерсона алгоритм


Форда — Фалкерсона алгоритм

Форда — Фалкерсона алгоритм [Ford — Fulkerson algo­rithm] — способ решения задачи построения максимального потока в сети. (Поток в сети определяется пропускной способностью ее дуг от начальной вершины до конечной вершины.). Алгоритм Л.Форда и Д.Фалкерсона применяется, например, при решении транс­портной задачи: требуется перевезти из начальной вершины сети в конечную груз по дугам сети за минимальное время. При этом по каждой дуге нельзя перевозить груза больше фиксированного объема.


Экономико-математический словарь: Словарь современной экономической науки. — М.: Дело. . 2003.

Смотреть что такое "Форда — Фалкерсона алгоритм" в других словарях:

  • Форда — Фалкерсона алгоритм — Способ решения задачи построения максимального потока в сети. (Поток в сети определяется пропускной способностью ее дуг от начальной вершины до конечной вершины.). Алгоритм Л.Форда и Д.Фалкерсона применяется, например, при решении транспортной… …   Справочник технического переводчика

  • Форда-Фалкерсона алгоритм — Алгоритм Форда Фалкерсона решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно… …   Википедия

  • Алгоритм Форда — Фалкерсона — решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно увеличивается посредством… …   Википедия

  • Алгоритм Форда–Фалкерсона — решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно увеличивается посредством… …   Википедия

  • Алгоритм Эдмондса — Карпа — Алгоритм Эдмондса  Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда  Фалкерсона и работает за время O(VE2). Впервые был опубликован в 1970 году советским… …   Википедия

  • Алгоритм Эдмондса — Алгоритм Эдмондса  Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда  Фалкерсона и работает за время . Впервые был опубликован в 1970 году советским учёным Е …   Википедия

  • Алгоритм проталкивания предпотока — решает задачу нахождения максимального потока в транспортной сети. Алгоритм не является частным случаем алгоритма Форда Фалкерсона. Реализованный без специальных усовершенствований, алгоритм выполняется за время . Некоторые усовершенствования ещё …   Википедия

  • Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 1970 году израильским (бывшим русским) учёным Ефимом Диницем. Временная сложность алгоритма составляет . Получить такую оценку позволяет введение… …   Википедия

  • Алгоритм Форда — У этого термина существуют и другие значения, см. Алгоритм Форда. Алгоритм Форда  Фалкерсона решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается… …   Википедия

  • Форда-Фалкерсона теорема — Теорема Форда Фалкерсона теорема о максимальном потоке в графе. Звучит так: величина максимального потока равна величине минимального разреза. Достаточность: любой поток между вершинами t и s меньше или равен величине любого сечения. Пусть дан… …   Википедия

Книги



Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.